'''
单链表反转：
通过递归找到头，并且在返回路径节点时，修改后一个节点的next为自己，自己的next为空。
'''

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        print("ret head: value=", head.val)
        return head
    print("head: value=", head.val)
    new_head = reverseList(head.next)  # 递归反转下一个节点
    print("head: value=", head.val, "new head=", new_head.val, "next head=", head.next.val)
    head.next.next = head              # 反转当前节点的指针
    head.next = None                   # 断开当前节点与其原下一个节点的连接
    return new_head

def printList(head: ListNode):
    curr = head
    while curr:
        print("value: ", curr.val)

        next_temp = curr.next  # 保存下一个节点
        curr = next_temp

a = ListNode(3)
b = ListNode(2, a)
c = ListNode(1, b)

printList(c)

d = reverseList(c)

printList(d)

e = reverseList(d)

printList(e)
